/*
题目: 子串的最大出现次数
给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数：

    子串中不同字母的数目必须小于等于 maxLetters 。
    子串的长度必须大于等于 minSize 且小于等于 maxSize 。

https://leetcode.cn/problems/maximum-number-of-occurrences-of-a-substring
 */
public class MaxFreq {
    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        //"abc" 肯定会覆盖 a，ab， 即长的肯定会覆盖短的，只要考虑最短的就好咯。
        Map<Character, Integer> map = new HashMap<> ();
        Map<String, Integer> freq = new HashMap<> ();
        int n = s.length();
        int left = 0;

        int src = 0;
        for (int i = 0; i < n; i ++) {
            char ch = s.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);

            // 窗口大小一直保持在 minSize 中, 就会处理所有长度为 minSize 的子串
            while (i - left + 1 > minSize || map.size() > maxLetters) {
                char lc = s.charAt(left ++);
                int cnt = map.get(lc);
                if (cnt == 1)   map.remove(lc);
                else            map.put(lc, cnt - 1);
            }

            if (i - left + 1 >= minSize) {
                String sub = s.substring(left, i + 1);
                int cnt = freq.getOrDefault(sub, 0) + 1;
                freq.put(sub, cnt);
                src = Math.max(cnt, src);
            }
        }

        return src;
    }
}
